package arithmetic.demo7;

import java.util.Arrays;


/**
 * 题目: 多情况统计dp_环形字符串中唯一的子字符串
 */
class Solution {
    public int findSubstringInWraproundString(String s) {

        int n = s.length();

        // 创建 dp
        int[] dp = new int[n];
        int[] hash = new int[26];

        // 初始化
        // 默认每一个位置都可以都有唯一的 1 个子串
        Arrays.fill(dp,1);


        // 填表
        for(int i = 1; i < n; i++) {
            // String str = s.substring(i-1, i+1);
            // 因为当前位置默认有 1
            // if(base.contains(str)) {
            //     // 一旦含有就加上前面含有的子字符串的个数
            //     dp[i] += dp[i-1];
            // }

            char ch1 = s.charAt(i-1), ch2 = s. charAt(i);

            if(ch1 + 1 == ch2 || (ch1 == 'z' && ch2 == 'a' )) {
                dp[i]  += dp[i-1];
            }
        }


        // 获取最大的子串的个数
        // 规律：相同结尾的最大子串的个数 包含 相同结尾的子串的个数
        // Hash 去重
        for(int i = 0; i < n ; i++) {
            char ch = s.charAt(i);
            if(dp[i] > hash[ch - 'a']) {
                hash[ch- 'a'] = dp[i];
            }
        }


        // Hash 内为最终结果， 累加即可
        int ret = 0;
        for(int i = 0; i< 26; i++) {
            ret += hash[i];
        }


        return ret;
    }
}
class Test {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.findSubstringInWraproundString("zaba"));
    }
}